lib/Mi manual de algoritmos/version_world_finals_2009/src/geometria/monotonechain.cpp

   1 // Convex Hull: Andrew's Monotone Chain Convex Hull
   2 // Complexity: O(n log n) (But lower constant than Graham Scan)
   3
   4 #include <algorithm>
   5 #include <vector>
   6 using namespace std;
   7
   8 typedef long long CoordType;
   9
  10 struct Point {
  11   CoordType x, y;
  12   bool operator <(const Point &p) const {
  13     return x < p.x || (x == p.x && y < p.y);
  14   }
  15 };
  16
  17 // 2D cross product.  Returns a positive value, if OAB makes a
  18 // counter-clockwise turn, negative for clockwise turn, and zero
  19 // if the points are collinear.
  20 CoordType cross(const Point &O, const Point &A, const Point &B){
  21   return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
  22 }
  23
  24 // Returns a list of points on the convex hull in
  25 // counter-clockwise order.  Note: the last point in the returned
  26 // list is the same as the first one.
  27 vector<Point> convexHull(vector<Point> P){
  28   int n = P.size(), k = 0;
  29   vector<Point> H(2*n);
  30   // Sort points lexicographically
  31   sort(P.begin(), P.end());
  32   // Build lower hull
  33   for (int i = 0; i < n; i++) {
  34     while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  35     H[k++] = P[i];
  36   }
  37   // Build upper hull
  38   for (int i = n-2, t = k+1; i >= 0; i--) {
  39     while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
  40     H[k++] = P[i];
  41   }
  42   H.resize(k);
  43   return H;
  44 }